package ca.swank.hq.ai;

import ca.swank.hardquor.*;
import java.util.TreeSet;
import java.util.Iterator;
import java.util.ArrayList;

import java.util.Comparator;

/**
 * An intelligent "AI" player that uses lookaheads to decide upon a move.
 *
 * The player is aware of three classes of moves:
 *   <LI>walk moves
 *   <LI>offensive wall moves
 *   <LI>defensive wall moves
 *
 * The number of lookaheads performed is of variable length. The player attempts
 * to build a lookahead tree of size 30, but expands the tree evenly so may build
 * trees much larger. If there is a limited number of moves until the completion
 * of a game, the lookahead tree may only have a few nodes.
 *
 */
public class TreeAIGame extends hqSimpleAIGame
{
  // weight scores for the walls remaining
  private static final int[] WEIGHTED_WALL_VALUES = new int[] { 0, 4, 7, 10, 13, 16, 19, 21, 23, 25, 26 };
  private static final int[] WEIGHTED_WALL_VALUES_LOSING = new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
  private static final int LOOKAHEAD_TREE_SIZE = 1;
  private static final int DEFENSIVE_WALL_THRESHHOLD = 1;

  public TreeAIGame(hardquorGameClient gameClient, int me, String userName)
  { super(gameClient, me, userName);
  }

  /**
  * notification that a move required by the current player.
  *
  * The player initially speaks a comment to the board, and then examines the board.
  * If a loss is inevitable, the sore-loser player gives up. Otherwise a 'best' move is made.
  */
  public void notifyTurn()
  {
    // say something witty to amuse them while I think
    //gameClient.speak(talker.getComment());

    /* Look ahead on a tree of constant size. This means that if there are several
     * different moves, each move is not examined deeply. If there are only a
     * few moves, more exhaustive lookaheads on such moves are made.
     * This keeps the time to generate a move near-constant.
     */
    LookaheadNode lookahead = new LookaheadNode(LOOKAHEAD_TREE_SIZE);
    ArrayList bestMoves = new ArrayList();
    int bestMoveWeight = lookahead.addBestMoves(bestMoves);

    // give up if losing is inevitable!
/*
    if(bestMoveWeight == SmartBoard.WEIGHT_MIN)
    { gameClient.speak("fuck this shit! I'm outa here!");
      gameClient.gameQuit();
      return;

    // i'm guaranteed to win!
    } else if(bestMoveWeight == SmartBoard.WEIGHT_MAX)
    { gameClient.speak("you're my bitch, bitch");
    }
*/
    // make a best move
    Move bestMove = (Move)bestMoves.get(dice.nextInt(bestMoves.size()));
    // wall move
    if(bestMove instanceof WallMove)
    { WallMove wallMove = (WallMove)bestMove;
      gameClient.tryMove(wallMove.a1(), wallMove.a2(), wallMove.b1(), wallMove.b2());
    // walk move
    } else if(bestMove instanceof WalkMove)
    { WalkMove walkMove = (WalkMove)bestMove;
      gameClient.tryMove(walkMove.source(), walkMove.target());
    }
  }


  /**
   * provides mechanics for looking ahead moves.
   *
   * The root lookahead node does not have a Move object, all other nodes do.
   * A node with no children is a leaf.
   */
  class LookaheadNode
  {
    private LookaheadNode[] childNodes;
    private boolean leaf;
    private Move move;

    /**
     * construct a new leaf node
     */
    public LookaheadNode(Move move)
    { leaf = true;
      this.move = move;
    }

    /**
     * construct a new root node. this will expand one level immediately
     * for a 1-level lookahead
     */
    public LookaheadNode()
    { leaf = true;
      expandOneLevel();
    }

    /**
     * construct a new root node. this will expand at least one level, and possibly
     * more until the tree has size desiredSize.
     */
    public LookaheadNode(int desiredSize)
    { leaf = true;
      boolean stillExpanding = expandOneLevel();
      while(getSize() < desiredSize && stillExpanding)
      { stillExpanding = expandOneLevel();
      }
    }

    /**
     * fetch a nodes's move.
     */
    public Move getMove()
    { return move;
    }

    /**
     * queries the size of a subtree
     */
    public int getSize()
    { if(leaf || childNodes.length==0)
      { return 1;
      } else
      { int size = 1;
        for(int i = 0; i < childNodes.length; i++)
        { size = size + childNodes[i].getSize();
        }
        return size;
      }
    }

    /**
     * expands the subtree one level. On leafs, this examines all 'good' moves reachable from this
     * lookahead level, and creates child nodes for each such move.
     *
     * for non-leaf nodes, all child nodes are expanded one level.
     *
     * When the game is near completion, it may not be possible to expand a tree any deeper: each
     * leaf may be at a game-complete state. This method will return false if no expansion takes
     * place.
     *
     * @returns true if tree has been expanded
     */
    public boolean expandOneLevel()
    {
      // on leaf nodes; try to expand to make this node no longer a leaf
      if(leaf)
      {
        // keep me a leaf if no child nodes
        if(board.getWinner() != hardquorBoard.PLAYER_NONE) return false;

        // make moves for lookaheads
        if(move != null) board.makeMove(move);

        // don't use me and you for lookahead
        int turn = board.getTurn();
        int wait = (turn + 1) % 2;

        // get all my moves
        ArrayList allMoves = board.getForwardWalkMoves(board.getPlayerLocation(turn), turn);
        if(board.getPlayerWalls(turn) > 0)
        { allMoves.addAll(board.getAllBlockingWalls(board.getPlayerLocation(wait), wait));
        }
        if(board.getPlayerWalls(turn) > 0 && board.getPlayerWalls(wait) > 0)
        { allMoves.addAll(board.getAllDefensiveWalls(board.getPlayerLocation(turn), turn, DEFENSIVE_WALL_THRESHHOLD, WEIGHTED_WALL_VALUES));
        }

        if(move != null) board.unMove(move);

        // transfer moves into child nodes
        childNodes = new LookaheadNode[allMoves.size()];
        for(int i = 0; i < childNodes.length; i++)
        { childNodes[i] = new LookaheadNode((Move)allMoves.get(i));
        }

        leaf = false;
        return true;

      // non-leaf nodes: attempt to expand all children. if no expansion is possible,
      // then return false
      } else
      { boolean expanded = false;

        // check to ensure move not null for expanding the root node
        if(move != null) board.makeMove(move);

        // expand all child nodes
        for(int i = 0; i < childNodes.length; i++)
        { if(childNodes[i].expandOneLevel())
          { expanded = true;
          }
        }

        // check to ensure move not null for expanding the root node
        if(move != null) board.unMove(move);

        return expanded;
      }
    }

    /**
     * only called on root node, which is not a leaf and does not have a move
     * this CLEARS the array.
     *
     * this adds the child node moves of best weight to the ArrayList provided.
     *
     * @return the weight of the moves in the best move ArrayList
     */
    public int addBestMoves(ArrayList bestMoves)
    {
      bestMoves.clear();

      int bestWeight = SmartBoard.WEIGHT_MIN;

      for(int i = 0; i < childNodes.length; i++)
      {
        int currentWeight = childNodes[i].getWeight();

        board.makeMove(childNodes[i].getMove());
        //System.out.println(board);
        board.unMove(childNodes[i].getMove());
        //System.out.println("WEIGHT: " + currentWeight);

        if(currentWeight == bestWeight)
        { bestMoves.add(childNodes[i].getMove());
        } else if(currentWeight > bestWeight)
        { bestMoves.clear();
          bestMoves.add(childNodes[i].getMove());
          bestWeight = currentWeight;
        }

      }
      return bestWeight;
    }

    /**
     * weighs a node.
     *
     * For leaf nodes, this simply weighs the node's move.
     * For non-leaf nodes, this returns the weight of the next level of lookahead moves. Because the
     * next level will be opponent moves, this score is the opponent's best move score negated.
     */
    public int getWeight()
    {
      // if leaf, just return the weight of this move
      if(leaf)
      { // used to negate weight comparisons for player 0
        int flip = 1;
        if(board.getTurn() == 0) flip = -1;
        int weight = flip*board.weighMove(move, WEIGHTED_WALL_VALUES);

        // maybe try weighing without wall scores if I am further ********************
        // if(board.getPlayerFurthestFromHome() == me)
        // { weight = flip*board.weighMove(move, WEIGHTED_WALL_VALUES_LOSING);
        // }
        // end try *******************************************************************

        return weight;

      // if not a leaf, return the best weight of all child nodes
      } else
      {
        board.makeMove(move);

        int bestMoveWeight = SmartBoard.WEIGHT_MAX;
        for(int i = 0; i < childNodes.length; i++)
        { int currentMoveWeight = -1*childNodes[i].getWeight();
          if(currentMoveWeight < bestMoveWeight)
          { bestMoveWeight = currentMoveWeight;
          }
        }

        board.unMove(move);

        return bestMoveWeight;
      }
    }
  }

}